/*
 * util.cpp
 *
 *  Created on: 2012-9-14
 *      Author: Futbal
 */

#include "../includes/util.h"

int GetMinOfTwo(int a, int b) {
	return a > b ? b : a;
}

int GetMinOfThree(int a, int b, int c) {
	int m = GetMinOfTwo(a, b);
	return m > c ? c : m;
}

void PrintValues(int* a, int from, int to) {
	for(int i = from; i < to; i++) {
		cout<<a[i]<<"\t";
	}
	cout<<endl;
}

bool IsPostVisitSeqOfBSTree(int* a, int from, int to){
//	assert(from >= 0 && from < to);

	int root = a[to - 1];
	int position = from;

	int i = to - 1;
	for(; i > from; i--) {
		if(a[i - 1] < root) {
			position = i;
			break;
		}
	}

	for(int j = i; j >= from; j--) {
		if(a[j - 1] > root) {
			return false;
		}
	}

	bool right = true;
	if(position < to - 1) {
		right = IsPostVisitSeqOfBSTree(a, position, to - 1);
	}
	bool left = true;
	if(position > from) {
		left = IsPostVisitSeqOfBSTree(a, from, position);
	}

	return left && right;
}

int GetMaxContinuousSum(int* a, int from, int to) {
	int max = 0, tempSum = 0;
	for(int i = from; i < to; i++) {
		tempSum += a[i];
		if(tempSum > max) {
			max = tempSum;
		} else if(tempSum < 0) {
			tempSum = 0;
		}
	}
	return max;
}

double GetMaxContinuousMul(double* a, int from, int to) {
	int len = to - from;
	double maxMul = 0.0, tempMul = 1.0;

	double* b = new double[len];

	bool* c = new bool[len];
	for(int i = 0; i < len; i++) {
		c[i] = a[i] > 0 ? true : false;
		b[i] = abs(a[i]);
	}

	double* curMul = new double[len];
	curMul[0] = b[0];
	for(int i = 1; i < len; i++) {
		tempMul = curMul[i - 1] * b[i];
		curMul[i] = (tempMul > curMul[i - 1]) ? tempMul : curMul[i - 1];
	}

	bool flag = c[0];
	maxMul = a[0];
	for(int i = 1; i < len; i++) {
		if((flag && c[i]) || (!flag && !c[i])) {
			if(curMul[i] > maxMul) {
				maxMul = curMul[i];
			}
		}
	}

	delete [] b;
	delete [] c;
	delete [] curMul;

	return maxMul;
}

bool ExistSumEqualsN(int* a, int from, int to, int n) {
	bool exist = false;
	int sum = 0, i = from, j = to - 1;
	while(i < j) {
		sum = a[i] + a[j];
		if(sum < n) {
			i++;
		} else if(sum > n) {
			j--;
		} else {
			exist = true;
			break;
		}
	}

	return exist;
}

int GetMaxMWithEqualSum(int* a, int from, int to) {
	int m = 1;

	return m;
}

int GetMaxHelper(int* b, int from, int to) {
	int max = b[from];
	for(int i = from + 1; i < to; i++) {
		if(b[i] > max) {
			max = b[i];
		}
	}

	return max;
}

int GetMaxContinuousSubSequence(int* a, int from, int to) {
	int max = 0;
	int* b = new int[to - from];
	b[0] = a[from];
	for(int i = from + 1; i < to - from; i++) {
		for(int j = 1; j < i; j++) {
			b[i] = GetMaxHelper(b, j, i) + ((a[i] < a[j]) ? 1 : 0);
		}
	}

	max = b[to - from - 1];
	delete [] b;
	return max;
}

void PrintContinueSumEqualsN(int n) {
	int minK = (int)((sqrt(pow(n - 1, 2.0) + 8 * n) - (n - 1)) / 2), maxK = (int)((sqrt(8 * n + 1) - 1) / 2);
	int x = 0;
	for(int k = minK; k <= maxK; k++) {
		x = 2 * n - k * (k - 1);
		if(x % (2 * k) == 0) {
			x /= (2 * k);
			for(int i = 0; i < k; i++) {
				cout<<x<<"\t";
				x += 1;
			}
			cout<<endl;
		}
	}
}

void LeftOddRightEven(int* a, int from, int to) {
	int i = from, j = to - 1;
	while(i < j) {
		if(a[i] % 2 == 0 && a[j] % 2 != 0) {
			a[i] ^= a[j];
			a[j] ^= a[i];
			a[i] ^= a[j];
			i++;
			j--;
		} else if(a[i] % 2 == 0) {
			j--;
		} else if(a[j] % 2 != 0) {
			i++;
		} else {
			i++;
			j--;
		}
	}
}

bool IsBit1(int value, int index) {
	value >>= index;
	return value & 1;
}

int GetFirstIndexOf1(int value) {
	int index = 0;
	while(index < 32 && ((value & 1) == 0)) {
		value >>= 1;
		index++;
	}
	return index;
}

void FindTwoNumsAppearsOnce(int* a, int from, int to, int& num1, int &num2) {
	int resultOfBitOR = 0;
	for(int i = from; i < to; i++) {
		resultOfBitOR ^= a[i];
	}

	int firstIndexOf1 = GetFirstIndexOf1(resultOfBitOR);
	num1 = 0;
	num2 = 0;

	for(int i = from; i < to; i++) {
		if(IsBit1(a[i], firstIndexOf1)) {
			num1 ^= a[i];
		} else {
			num2 ^= a[i];
		}
	}
}

int FindNthUglyNum(int n) {
	int* ugly = new int[n];
	int nth = 0;

	ugly[0] = 1;
	int index2 = 0, index3 = 0, index5 = 0, index = 1;
	while(index < n) {
		int val = GetMinOfThree(ugly[index2] * 2, ugly[index3] * 3, ugly[index5] * 5);
		if(val == ugly[index2] * 2) {
			index2++;
		}
		if(val == ugly[index3] * 3) {
			index3++;
		}
		if(val == ugly[index5] * 5){
			index5++;
		}
		ugly[index++] = val;
	}

	nth = ugly[n - 1];
	delete [] ugly;
	return nth;
}

int GetTroubleMakerNumMerge(int* a, int from, int mid, int to) {
	int i = from, j = mid + 1;
	int k = 0, num = 0;
	int* p = new int[to - from + 1];

	while(i < mid && j < to) {
		if(a[i] < a[j]) {
			p[k++] = a[i++];
		} else {
			num += mid - i + 1;

			p[k++] = a[j++];
		}
	}
	while(i <= mid) {
		p[k++] = a[i++];
	}
	while(j < to) {
		p[k++] = a[j++];
	}

	for(k = from; k < to; k++) {
		a[k] = p[k - from];
	}

	delete [] p;
	return num;
}

int GetTroubleMakerNum(int* a, int from, int to) {
	if(from < to) {
		int mid = (from + to) / 2;
		int num = GetTroubleMakerNum(a, from, mid) + GetTroubleMakerNum(a, mid + 1, to);
		num += GetTroubleMakerNumMerge(a, from, mid, to);
		return num;
	}
	return 0;
}

bool IsAscendingSequenceRecursively(int* a, int from, int to) {
	if(from < to - 1) {
		return (a[from] < a[from + 1]) && (a[to - 2] < a[to - 1]) &&
				IsAscendingSequenceRecursively(a, from + 1, to - 1);
	}
	return true;
}

int* Generate(int a, int b, int N, int* Q) {
	Q = new int[N];
	int step = 1;
	if(a > b) {
		a ^= b;
		b ^= a;
		a ^= b;
	} else if(a == b) {
		step = a;
	}
	int k = a;
	for(int i = 0; i < N; ) {
		if(k % a == 0 || k % b == 0) {
			Q[i++] = k;
		}
		k += step;
	}

	return Q;
}
